package com.itzmn.newcode.offer1;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/18 15:46
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 矩形覆盖
 *
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 *
 * 这是一个斐波那契数列
 *
 *
 */
public class _10_RectangularCover {

    public static void main(String[] args) {
        new _10_RectangularCover().test();
    }

    private void test() {

        RectCover(5);
    }
    public int RectCover(int target) {
        if (target == 1){
            return 1;
        }
        if (target == 2){
            return 2;
        }

        int old1 = 2;
        int old2 = 1;

        int sum = 0;
        for (int i=3;i<=target;i++){
            sum = old1+old2;
            old2 = old1;
            old1 = sum;
        }
        return sum;
    }


}
